package com.leetcode.code;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 *
 * @author zkingcobra
 * Date: 2020/6/5 10:15 上午
 */
public class LeetCode0054Java {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.spiralOrder(new int[][] { { 1, 2, 3, 4 }, { 4, 5, 6, 4 }, { 7, 8, 9, 4 } }));
    }

    private static class Solution {

        /**
         * 方法一：模拟
         */
        public List<Integer> spiralOrder(int[][] matrix) {

            List<Integer> order = new ArrayList<Integer>();
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return order;
            }
            int rows = matrix.length;
            int columns = matrix[0].length;
            boolean[][] visited = new boolean[rows][columns];
            int total = rows * columns;
            int row = 0, column = 0;
            int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
            int directionIndex = 0;
            for (int i = 0; i < total; i++) {
                order.add(matrix[row][column]);
                visited[row][column] = true;
                int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
                if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns
                        || visited[nextRow][nextColumn]) {
                    directionIndex = (directionIndex + 1) % 4;
                }
                row += directions[directionIndex][0];
                column += directions[directionIndex][1];
            }
            return order;
        }

        /**
         * TODO 方法二：按层模拟
         */
        public List<Integer> spiralOrder2(int[][] matrix) {
            List<Integer> order = new ArrayList<Integer>();
            return order;
        }
    }
}
